1 // Equipo Poncho, Carriel y Ruana
22 template <class T
> string
toStr(const T
&x
)
23 { stringstream s
; s
<< x
; return s
.str(); }
24 template <class T
> int toInt(const T
&x
)
25 { stringstream s
; s
<< x
; int r
; s
>> r
; return r
; }
27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
29 #define D(x) cout << #x " = " << (x) << endl;
31 const double EPS
= 1e-9;
33 int cmp(double x
, double y
= 0, double tol
= EPS
) {
34 return (x
<= y
+ tol
) ? (x
+ tol
< y
) ? -1 : 0 : 1;
37 #define INPUT_FILE "compression"
39 const int MAXBASES
= 105, oo
= 1 << 28;
43 int bit
[20]; // bit[i] = index of term i in the document
45 int memo
[MAXBASES
][1 << 16];
50 int f(int b
, int mask
, int doc
) {
51 if (mask
== doc
) return 0;
52 if (b
== B
) { // Vi todas las bases
56 //printf("b = %d\n", b);
57 if (memo
[b
][mask
] != -1) return memo
[b
][mask
];
59 if ((bases
[b
] | doc
) != doc
) {
60 return memo
[b
][mask
] = f(b
+ 1, mask
, doc
);
63 //assert(compatible(bases[b]));
66 int ans
= f(b
+ 1, mask
| bases
[b
], doc
) + 1;
69 ans
= min(ans
, f(b
+ 1, mask
, doc
));
70 return memo
[b
][mask
] = ans
;
75 //For(i, 0, B) if (compatible(bases[i])) printf("Base i=%d: %d\n", i, maskOfBase(bases[i]));
77 // for (int i = 0; i < 16; ++i) {
78 // printf("bit[%d] = %d\n", i, bit[i]);
81 int ans
= f(0, 0, doc
);
82 if (ans
>= oo
) ans
= 0;
87 freopen(INPUT_FILE
".in", "r", stdin
);
88 while (cin
>> B
>> D
) {
89 if (B
== 0 and D
== 0) break;
90 for (int i
= 0; i
< B
; ++i
) {
98 //printf("base[i=%d] = %d\n", i, bases[i]);
101 for (int j
= 0; j
< D
; ++j
) {
106 int x
; cin
>> x
; x
--;
109 //printf("doc = %d\n", doc);
110 for (int b
= 0; b
< B
; ++b
) {
111 for (int mask
= 0; mask
< (1 << 16); ++mask
) {
116 if (j
+ 1 < D
) printf(" ");